#pragma once

#include <vector>

namespace solution_078
{

class Solution
{
public:
    std::vector< std::vector<int> > subsets(const std::vector<int>& nums)
    {
        m_nums = &nums;
        m_subsets.emplace_back();
        for (int i = 1; i <= (int)nums.size(); ++i) {
            std::vector<int> path;
            backtrack(path, 1, nums.size(), i);
        }
        return m_subsets;
    }

private:
    void backtrack(std::vector<int>& path, int first, int n, int k)
    {
        int curr_len = path.size();
        int rest_len = k - curr_len;
        if (curr_len == k) {
            m_subsets.push_back(path);
            return;
        }

        for (int i = first; i <= n - rest_len + 1; ++i) {
            path.push_back(m_nums->at(i - 1));
            backtrack(path, i + 1, n, k);
            path.pop_back();
        }
    }

    const std::vector<int>* m_nums;
    std::vector< std::vector<int> > m_subsets;
};

}  /* namespace solution_078 */
